Digital networks, including local area networks (LANs), wide area networks (WANs), and of course, the Internet, serve to connect various devices which communicate with each other using digital signals. The capacity or bandwidth of a network link dictates how much information it can carry at any given time. Devices known as routers typically form the nodes to which the network links connect. Such a node may be connected to other network nodes, or directly to local traffic. Various protocols are used along the various paths, and even over the same paths.
Asynchronous transfer mode (ATM) is a cell-based networking technology which supports many types of information transfers at very high speeds. Messages are broken into xe2x80x9ccellsxe2x80x9d of 53 8-bit xe2x80x9coctetsxe2x80x9d, a 5-byte header and a 48-byte information payload. The header includes a generic flow control (GFC) field and a virtual channel identifier (VCI) field, as well as other fields.
Subtending is a mechanism which allows the linking of a number of interface units into one network trunk port by allowing xe2x80x9clower-levelxe2x80x9d interface units to connect to xe2x80x9chigher-levelxe2x80x9d units, so that ultimately all of the traffic handled at a particular site passes to the trunk through a single interface unit. This feature allows improved per-port costs for service providers by reducing the number of ports required in an aggregator network where multiple interfaces are installed in one location. Subtending links one or more interface units in one area into one network trunk connection.
One of the most common problems in connecting networking systems together through subtending is known as the xe2x80x9cparking lotxe2x80x9d problem. As each system gets further away from the trunk interface, it only receives half of the available upstream bandwidth from the system above it. A system once removed from the trunk receives xc2xd of the available upstream bandwidth, while a system twice removed receives xc2xc of the available upstream bandwidth, etc.
Most ATM architectures solve this problem using per VC queuing, in which a separate queue is maintained for every virtual channel. However, per VC queuing is complex and costly.
To avoid the parking lot problem, upstream traffic is enqueued by its source interface unit in the chain. A round robin scheduler is used to dequeue the traffic and send it to the interface unit above it giving each interface unit an equal share of the available upstream bandwidth. To ensure fairness between each interface unit and the traffic local to the interface unit the round robin scheduler is rate locked to the speed of the local trunk.
In an asynchronous transfer mode (ATM) environment, an interface unit identifier is stored in the generic flow control (GFC) field of each ATM cell. This identifier is passed on until it is received at the interface unit connecting to the network trunk, at which point the GFC field can be cleared for transmission of the cell.
Input queues are used to queue ATM cells received from lower level, or subtended, units as well as ATM cells received from local traffic. Each interface unit has at least an input queue for each subtended interface unit, plus an input queue for its own local traffic. As cells are received from each interface unit, they are stored in the appropriate input queue based on the identifier in the GFC field of the ATM header.
Accordingly, to ensure fair access to upstream trunk bandwidth among a plurality of interface units, a plurality of queues is provided in a first unit. One of the queues is associated with the first interface unit. Each of the remaining queues is associated with one of a plurality of second interface units. Local data is received by the first interface unit and forwarded to the respective queue. Data received from a second, subtended interface unit is forwarded to a queue which is associated with the second interface unit. Data is then issued from the queues according to a fairness algorithm.
In one embodiment, a unique identifier is assigned to each interface unit. Associating a queue with an interface unit is done by associating the queue with the respective interface unit""s identifier. In each interface unit, local data is tagged with that interface unit""s identifier, and received data is forwarded to a queue according to the data""s tag.
Where data is formatted as asynchronous transfer mode (ATM) cells, it can be tagged by inserting the receiving interface unit""s identifier into the generic flow control (GFC) field of each cell.
Alternatively, a table of associations between virtual channel identifiers (VCIs) and interface unit identifiers can be maintained. The received data is forwarded to a queue according to the interface unit identifier associated with the data""s VCI.
In one embodiment, the fairness algorithm is a round robin algorithm.
Interface units may be interconnected such that a top-level interface unit connects to a network trunk, while each non-top-level interface unit connects directly to an interface unit at a next higher level.
The interface units can be arranged in a tree, daisy-chain or star configuration.
Each queue can also be divided into two or more sub-queues, each sub-queue associated with a different priority. Data is then issued from a queue""s highest priority sub-queue that contains data.
One advantage of the present invention is configurability. The user need only specify a unique interface unit identifier through, for example, a command line interface. Software and hardware execute the algorithm without any further intervention.
Another advantage is that the algorithm of the present invention works for any trunk speed. As users move from slower (T1) to faster (OC3) trunk interfaces, they need not reconfigure the box. The hardware is self-timed to the speed of the trunk interface and always ensures fairness.
Another advantage is that because any unit can operate as fast as its subtended link speed, units at the bottom of a tree topology can send data upstream as fast as its subtended link. If no other units in the system are sending traffic upstream, the bottom or lowest-level unit will have full bandwidth use of the upstream network trunk.
Another advantage is that the present invention works well regardless of topology, e.g., a star, tree, or daisy chained topology. The fairness algorithm remains unchanged.
An embodiment of the present invention also supports priority among the various subscribers in a subtended configuration as well. If a subscriber at the bottom interface unit is running high priority voice traffic, while a subscriber at the top unit is running low priority TCP/IP traffic, the high priority traffic will take precedence over the lower priority traffic within the subtended configuration. This results because the input queues are actually per priority per interface unit input queues. Higher priority traffic accesses the upstream trunk bandwidth before lower priority traffic.